Obeleži sve kategorije koje odgovaraju problemu

Фенвикова стабла

Фенвикова дрвета тј. бинарно индексирана дрвета (енгл. binary indexed tree, BIT) користе мало мање меморије и могу бити за константни фактор бржа од сегментних дрвета (иако је сложеност операција асимптотски једнака). Са друге стране, за разлику од сегментних дрвета која су погодна за различите операције, Фенвикова дрвета су специјализована само за асоцијативне операције које имају инверз (нпр. збирови или производи елемената сегмената се могу налазити уз помоћ BIT, али не и минимуми, нзд-ови и слично). Сегментна дрвета могу да ураде све што и Фенвикова, док обратно не важи.

Иако се назива дрветом, Фенвиково дрво заправо представља низ вредности збирова неких паметно изабраних сегмената. Избор сегмената је у тесној вези са бинарном репрезентацијом индекса. Поново ћемо једноставности ради претпоставити да се вредности у низу смештају од позиције \(1\) (вредност на позицији \(0\) jе ирелевантна) и то и у полазном низу и у низу у ком се смешта дрво. Прилагођавање кода ситуацији у којој су у полазном низу елементи смештени од позиције нула, веома је једноставно (само је на почетку сваке функције која ради са дрветом индекс полазног низа потребно увећати за један пре даље обраде). Ако је полазни низ дужине \(n\), елементи дрвета ће се смештати у посебан низ на позиције \([1, n]\).

Кључна идеја Фенвиковог дрвета је следећа: у дрвету се на позицији \(k\) чува збир вредности полазног низа из сегмента позиција облика \((f(k), k]\) где је \(f(k)\) број који се добије од броја \(k\) тако што се из бинарног записа броја \(k\) обрише прва јединица здесна.

На пример, на месту \(k=21\) записује се збир елемената полазног низа на позицијама из интервала \((20, 21]\), јер се број \(21\) бинарно записује као \(10101\) и брисањем јединице добија се бинарни запис \(10100\) тј. број \(20\) (важи да је \(f(21) = 20\)). На позицији број \(20\) налази се збир елемената са позиција из интервала \((16, 20]\), јер се брисањем јединице добија бинарни запис \(10000\) тј. број \(16\) (важи да је \(f(20) = 16\)). На позицији \(16\) се чува збир елемената са позиција из интервала \((0, 16]\), јер се брисањем јединице из бинарног записа броја \(16\) добија \(0\) (важи да је \(f(16) = 0\)).

За низ \(3, 4, 1, 2, 6, 5, 1, 4\), Фенвиково дрво би чувало следеће вредности.

0    1      2     3     4     5     6     7     8  k
     1     10    11   100   101   110   111  1000  k  binarno
     0      0    10     0   100   100   110     0  f(k) binarno
 (0,1]  (0,2] (2,3] (0,4] (4,5] (4,6] (6,7] (0,8]  interval
     3      4     1     2     6     5     1     4  niz
     3      7     1    10     6    11     1    26  drvo

Надовезивањем интервала \((0, 16]\), \((16, 20]\) и \((20, 21]\) добија се интервал \((0, 21]\) тј. префикс низа до позиције \(21\). Збир елемената у префиксу се, дакле, може добити као збир неколико елемената записаних у Фенвиковом дрвету. Ово, наравно, важи за произвољни индекс (не само за \(21\)). Број елемената чијим се сабирањем добија збир префикса је само \(O(\log{n})\). Наиме, у сваком кораку се број јединица у бинарном запису текућег индекса смањује, а број \(n\) се записује са највише \(O(\log{n})\) бинарних јединица.

Имплементација је веома једноставна, када се пронађе начин да се из бинарног записа броја уклони прва јединица здесна тј. да се за дати број \(k\) израчуна \(f(k)\). Под претпоставком да су бројеви записани у потпуном комплементу, изразом k & -k може се добити број који садржи само једну јединицу и то на месту последње јединице у запису броја k. Одузимањем те вредности од броја k тј. изразом k - (k & -k) добијамо ефекат брисања последње јединице у бинарном запису броја k и то представља имплементацију функције \(f\). Други начин да се то уради је да се израчуна вредност k & (k-1).

Збир префикса \([0, k]\) полазног низа можемо онда израчунати наредном функцијом.

// na osnovu Fenvikovog drveta smeštenog u niz drvo
// izračunava zbir prefiksa (0, k] polaznog niza
int zbirPrefiksa(int drvo[], int k) {
  int zbir = 0;
  while (k > 0) {
     zbir += drvo[k];
     k -= k & -k;
  }
}

Када знамо збир префикса, збир произвољног сегмента \([a, b]\) можемо израчунати као разлику збира префикса \((0, b]\) и збира префикса \((0, a-1]\). Пошто се оба рачунају у времену \(O(\log{n})\), и збир сваког сегмента можемо израчунати у времену \(O(\log{n})\). Напоменимо и то да је због ове операције важно да асоцијативна операција која се користи у Фенвиковом дрвету има инверз (у овом случају да бисмо могли да одузимањем две вредности префикса добијамо збир произвољног сегмента).

Основна предност Фенвикових дрвета у односу на низ свих збирова префикса је то што се могу ефикасно ажурирати. Размотримо функцију која ажурира дрво након увећања елемента у полазном низу на позицији \(k\) за вредност \(x\). Тада је за \(x\) потребно увећати све оне збирове у дрвету у којима се као сабирак јавља и елемент на позицији \(k\). Ти бројеви се израчунавају веома слично као у претходној функцији, једино што се уместо одузимања вредности k & -k број k у сваком кораку увећава за k & -k.

На пример, ако би се у претходном примеру елемент на позицји \(3\) увећао за вредност \(4\), било би потребно повећати за \(4\) вредности елемената Фенвиковог дрвета на позицијама \(3\), \(4\) и \(8\). До ових позиција бисмо дошли почев од бинарног записа броја \(3\) који износи \(11\) сабирањем са \(1\) (број који садржи тачно једну јединицу на позицији последње јединице у бинарном запису датог броја) чиме бисмо добили \(100\) што одговара броју \(4\), а након тога бисмо ову вредност сабрали са \(100\) чиме бисмо добили \(1000\) (бинарни запис броја \(8\)). Овде се процедура завршава с обзиром на то да смо стигли до последњег елемента у Фенвиковом дрвету.

// Ažurira Fenvikovo drvo smešteno u niz drvo nakon što se
// u originalnom nizu element na poziciji k uveća za x
void dodaj(int drvo[], int n, int k, int x) {
  while (k <= n) {
    drvo[k] += x;
    k += k & -k;
  }
}

Објаснимо и докажимо коректност претходне имплементације. Потребно је ажурирати све оне позиције \(m\) чији придружени сегмент садржи вредност \(k\), тј. све оне позиције \(m\) такве да је \(k \in (f(m), m]\), тј. \(f(m) < k \leq m\). Ово никако не може да важи за бројеве \(m < k\), а сигурно важи за број \(m = k\), јер је \(f(k) < k\), када је \(k > 0\) (а ми претпостављамо да је \(1 \leq k \leq n\)). За бројеве \(m > k\), сигурно важи десна неједнакост и потребно је утврдити да важи лева. Нека је \(g(k)\) број који се добија од \(k\) тако што се \(k\) сабере са бројем који има само једну јединицу у свом бинарном запису и то на позицји на којој се налази последња јединица у бинарном запису броја \(k\). На пример, за број \(k = 101100\), број \(g(k) = 101100 + 100 = 110000\). У имплементацији се број \(g(k)\) лако може израчунати као k + (k & -k). Тврдимо да је најмањи број \(m\) који задовољава услов \(f(m) < k < m\) управо \(g(k)\). Заиста, очигледно важи \(k < g(k)\) и \(g(k)\) има све нуле од позиције последње јединице у бинарном запису броја \(k\) (укључујући и њу), па до краја, па се брисањем његове последње јединице, тј. израчунавањем \(f(g(k))\) сигурно добија број који је строго мањи од \(k\). Ниједан број \(m\) између \(k\) и \(g(k)\) не може да задовољи услов да је \(f(m) < k\). Наиме, сви ти бројеви се поклапају са бројем \(k\) на свим позицијама пре крајњих нула, а на позицијама крајњих нула броја \(k\) имају бар неку јединицу, чијим се брисањем добија број који је већи или једнак \(k\). По истом принципу закључујемо да наредни тражени број мора бити \(g(g(k))\), затим \(g(g(g(k)))\) итд. све док се не добије неки број који превазилази \(n\). Заиста, важи да је \(k < g(k) < g(g(k))\). Важи да је \(f(g(g(k))) < f(g(k)) < k\), па \(g(g(k))\) задовољава услов. Ниједан број између \(g(k)\) и \(g(g(k))\) не може да задовољи услов, јер се сви они поклапају са \(g(k)\) у свим бинарним цифрама, осим на његовим крајњим нулама где имају неке јединице. Брисањем последње јединице се добија број који је већи или једнак \(g(k)\), па добијени број не може бити мањи од \(k\). Отуда следи да су једине позиције које треба ажурирати управо позиције из серије \(k\), \(g(k)\), \(g(g(k))\) итд., све док су оне мање или једнаке \(n\), па је наша имплементација коректна.

Остаје још питање како у старту формирати Фенвиково дрво, међутим, формирање се може свести на то да се креира дрво попуњено само нулама, а да се затим увећава вредност једног по једног елемента низа претходном функцијом.

// Na osnovu niza a u kom su elementi smešteni
// na pozicijama iz segmenta [1, n] formira Fenvikovo drvo
// i smešta ga u niz drvo (na pozicije iz segmenta [1, n])
void formirajDrvo(int drvo[], int n, int a[]) {
  fill_n(a+1, n, 0);
  for (int k = 1; k <= n; k++)
     dodaj(drvo, n, k, a[k]);
}